package com.LeeCode;

import java.util.PriorityQueue;

/**
 * 重新安排会议得到最多空余时间 II
 */

public class Code3440 {
    public static void main(String[] args) {
        int eventTime = 10;
        int[] startTime = {0, 3, 7, 9}, endTime = {1, 4, 8, 10};
        System.out.println(new Code3440().maxFreeTime(eventTime, startTime, endTime));
    }

    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {

        // 记录三个最大的空区间
        int[][] max3FreeTime = getMax3FreeTime(eventTime, startTime, endTime);
        int n = startTime.length;

        int ans = startTime[0];

        for (int i = 0; i < n; i++) {
            int left = i == 0 ? 0 : endTime[i - 1];
            int index = -1;
            for (int[] freeTime : max3FreeTime) {
                if (freeTime[0] + freeTime[1] != startTime[i] && freeTime[0] != endTime[i] // 空位不在左右
                        && freeTime[1] >= endTime[i] - startTime[i]) {  // 空位可以放下
                    index = freeTime[0];
                }
            }

            int rightEnd = i == n - 1 ? eventTime : startTime[i + 1];

            if (index == -1) {  // 不能挪到其他区间
                ans = Math.max(ans, rightEnd - left - endTime[i] + startTime[i]);
            } else {  // 挪到其他区间
                ans = Math.max(ans, rightEnd - left);
            }
        }
        return ans;
    }

    private int[][] getMax3FreeTime(int eventTime, int[] startTime, int[] endTime) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        int[][] ans = new int[3][];
        int n = startTime.length;

        pq.offer(new int[]{0, startTime[0]});
        pq.offer(new int[]{endTime[n - 1], eventTime - endTime[n - 1]});

        for (int i = 1; i < n; i++) {
            pq.offer(new int[]{endTime[i - 1], startTime[i] - endTime[i - 1]});
        }
        for (int i = 0; i < 3; i++) {
            ans[i] = pq.poll();
        }
        return ans;
    }
}
